This section describes the theoretical and technical problems that need to be considered in the process of constructing a solution for keyword based searching in Pastry.   

Finding an answer to the question of where and how to store indexes in the Pastry ring is fundamental. Clearly, nodes that store a higher number of indexes are potentially burdened far beyond nodes that store none or a smaller number of indexes. Thus, in order for the system to be scalable the solution should try to distribute indexes equally among several nodes. Both the structure of such a distributed index as well as the algorithms that operate on it are key problems that need to be closely investigated as they affect multiple, potentially correlating properties of the system i.e.\
\begin{itemize}
 \item the spread and evenness of computational and memory load among peers  
 \item the amount of bandwidth consumed 
 \item the response time and successfulness of the three basic actions tag, untag and search
\end{itemize}
The task of determining an optimal configuration as well as the overall quality of an index distribution is non-trivial. Theoretic algorithm analysis may help to find appropriate results, however, test experiments with realistic scenarios will be necessary to confirm the findings.

\subsection{Search tree structure}
One obvious structure for solving the problem of index distribution is a search tree. A description of its basic operation follows.

When a keyword $K$ is used for the first time in the process of storing an object, an index for it is constructed on a node $n$ which becomes the root of the tree. As more and more objects are tagged under $K$, the storage load on $n$ increases. When this load exceeds a certain threshold, $n$ distributes its content equally among two ore more other nodes, which become its children. We coin this \textit{index expansion}. When the storage load on the children exceeds the threshold, they too distribute their content. Searching is enabled by querying the root $n$, which forwards the query to its children recursively. Ultimately, the leaves of the tree send their index entries to the requester.

%\begin{figure}[h]
% \begin{center}
%  \begin{graph}(0,3)(0,-2)
%   \graphnodesize{0.1}
%
%   \roundnode{requester}(0,0)[\graphnodesize{0.5}\graphnodecolour{1}]
%   \autonodetext{requester}[n]{Requester}
%
%   \roundnode{root}(0,-2)[\graphnodesize{0.5}\graphnodecolour{1}]
%   \autonodetext{root}[s]{Root}
%
%   \diredge{requester}{root} 
%   \dirloopedge{root}{30}(1,0)
%
%   \edgetext{requester}{root}{1. $store(object A, keyword K)$}
%   \freetext(3,-2){2. $create(I_{obj})$}
%
%  \end{graph}
% \end{center}
% \caption{Tag - object index creation}
%\end{figure}

\begin{figure}[h]
 \begin{center}
  \begin{graph}(7,6)(0,-6)
   \graphnodesize{0.1}
   \roundnode{root}(4,-2)[\graphnodesize{0.9}\graphnodecolour{1}]\autonodetext{root}{$I_{child}$}
   \roundnode{child11}(2,-4)[\graphnodesize{0.9}\graphnodecolour{1}]\autonodetext{child11}{$I_{child}$}
   \roundnode{child12}(6,-4)[\graphnodesize{0.9}\graphnodecolour{1}]\autonodetext{child12}{$I_{child}$}
   \diredge{root}{child11} 
   \diredge{root}{child12} 
   \rectnode{child21}[.6,.5](1,-6)[\graphnodecolour{1}]\autonodetext{child21}{$I_{obj}$}
   \rectnode{child22}[.6,.5](3,-6)[\graphnodecolour{1}]\autonodetext{child22}{$I_{obj}$}
   \diredge{child11}{child21} 
   \diredge{child11}{child22} 
   \rectnode{child23}[.6,.5](5,-6)[\graphnodecolour{1}]\autonodetext{child23}{$I_{obj}$}
   \rectnode{child24}[.6,.5](7,-6)[\graphnodecolour{1}]\autonodetext{child24}{$I_{obj}$}
   \diredge{child12}{child23} 
   \diredge{child12}{child24} 

   \autonodetext{root}[n]{root node}
   \autonodetext{child21}[s]{$1$}
   \autonodetext{child22}[s]{$C=2$}
   \autonodetext{child23}[s]{$1$}
   \autonodetext{child24}[s]{$C=2$}

   \freetext(0,-1){\textbf{L}}
   \freetext(0,-2){$0$}
   \freetext(0,-4){$1$}
   \freetext(0,-6){$H=2$}
  \end{graph}
 \end{center}
 \caption{Distributed index in search tree structure}
 \label{fig:searchtreestructure}
\end{figure}

%\begin{figure}[h]
% \begin{center}
%  \begin{graph}(4,4)(0,-3)
%   \graphnodesize{0.1}
%   \roundnode{requester}(2,0)[\graphnodesize{0.6}\graphnodecolour{0.8}]\autonodetext{requester}{$S$}
%   \roundnode{root}(2,-2)[\graphnodesize{0.6}\graphnodecolour{1}]\autonodetext{root}{$R$}
%   \squarenode{childa}(0,-3)[\graphnodesize{0.6}\graphnodecolour{1}]\autonodetext{childa}{$A$}
%   \squarenode{childb}(4,-3)[\graphnodesize{0.6}\graphnodecolour{1}]\autonodetext{childb}{$B$}
%   \diredge{requester}{root}[\graphlinedash{1}]
%   \edge{root}{childa} 
%   \edge{root}{childb}
%   \dirbow{root}{childb}{0.5}[\graphlinedash{1}]
%   \dirbow{root}{childa}{-0.5}[\graphlinedash{1}]
%   \dirbow{childb}{requester}{-0.5}[\graphlinedash{5}]
%   \dirbow{childa}{requester}{0.5}[\graphlinedash{5}]
%  \end{graph}
% \end{center}
% \caption{Message flow searching}
%\end{figure}

\subsection{Definitions}

An index on a node is either an object index $I_{obj}$ located on a leaf node or a child node index $I_{child}$ located on a parent node. An object index stores references to objects and a child node index stores references to child nodes. A node can have zero ore more indexes.

Let $N$ be the number of active nodes in the system, $\upsilon$ be defined as the maximum size of an object index, $\phi$ as the maximum size of a child node index, $C$ the maximum number of children per node, $L$ be the level of the current node in the tree, $H$ the maximum height of the tree. 
Figure~\ref{fig:searchtreestructure} outlines an index structured as a search tree, excluding the parameters $\upsilon$ and $\phi$. The following chapters shall base their discussion on the search tree structure and the definitions described above.

%Also let $S$ be the total amount of data stored in the system, $S_i$ the amount of data stored on a node $i$, $M$ be the overall storage capacity available in the system, and $M_i$ the capacity available on node $i$. 
%
%In terms of memory consumption the perfect distribution is then defined by the factor 
%\[S_{\mu}=\frac{S}{N}\]
%with the standard deviation 
%\[S_{\sigma}=\sqrt{\frac{1}{N}\sum_{i=1}^{N}(S_i-S_{\mu})}\] 
%which is a measurement for the quality of distribution as it indicates how much the nodes deviate from $S_{\mu}$. 
%


\subsection{Index structure}

\subsubsection{Index size}
One of the first questions that needs to be clearified is if the index structure is capable of storing a large enough number of objects in terms of quantity disregarding node capabilities. Assuming that the tree stores its entries only on the leaves, the number of entries is limited by 
\begin{eqnarray}
\upsilon \times C^H
\end{eqnarray} 


\subsubsection{Distribution technique}
The attribute upon the content of an object indexed is divided must be common to all objects stored in them. What is a suitable attribute that allows a high quality of distribution?

One candidate is the title of objects. Using this property, when an object index at the $L$th level of a tree expands, it partitions its entries into sets based on the $L$th character of the title of each entry. It then sends each set to a different node, which becomes its child. It keeps a reference to its children and becomes a child index.

Unfortunately, this attribute has some limitations. The distribution of the content among the children would be unequal as the distribution of words beginning with a different letter or combination of letters is never uniform in human languages. Another problem occurs when an expanding object index at the $L$th level has an entry with a title of less than $L$ characters. The node does not have an extra character based on which to put it in one of the sets. Finally, using titles are unique ids for entries means that a single index could not contain different objects with the same names. 

A better approach is to use a cryptographic hash on objects. Using hash values, when an object index at the $L$th level of a tree expands, it partitions its entries into sets based on the $L$th digit of the hash of each entry. Since such functions map their input uniformly across a large id-space \cite{cormenalg}, the distribution of entries among children should be equal, and the probability of collisions is likely to be low. Moreover, it supports different objects with identical titles. Finally, letting the number of digits of hash value be $T$, expanding object on the $L$th level will certainly be able to map entries to children for $L<T$.  

Cryptographic hash functions strive to minimize the probibilty of collisions by mapping data uniformly across a large output range. Nevertheless, collisions may still occur. Therefore, handling collisions is important and will be addressed at the solution.

\subsubsection{Thresholds}
\label{sec:pa-thresholds}
How large may an object index grow before its content must be distributed?  
Let $S_{n}$ be defined as the storage capacity on a node $n$, $I_{obj}^n$ be the set of object indexes and $I_{child}^n$ be the set of child node indexes on a node $n$. The upper bound for the threshold $\upsilon$ on node $n$ is then determined by 
\begin{eqnarray}
 \upsilon \leq \frac{S_n - \phi \times |I_{child}^n|}{|I_{obj}^n|} 
 \label{eq:upperboundthreshold}
\end{eqnarray} 
Equation~\ref{eq:upperboundthreshold} shows that the upper bound of $\upsilon$ changes \textit{dynamically} with respect to the number of indexes that are located on a node. 

The distribution of an object index is only sensible if the consumed storage load on the node decreases with the index expansion. As a result the following requirement must hold:
\begin{eqnarray}
 \upsilon > \phi
\end{eqnarray} 

When $I_{child}^n$ consumes the entire capacity the node $n$ is full and can not store any further indexes. 
For a node $n$ to be able to store an additional object index the following inequality must hold:
\begin{eqnarray}
 S_n - \phi \times |I_{child}^n| + \upsilon \times I_{obj}^n \geq \upsilon  
\end{eqnarray} 


Having a better understanding for the upper bound, what is a good value for $\upsilon$ in terms of distribution and performance?
Certainly, if $\upsilon$ is too high the index will be less distributed, the quality of the distribution will suffer. On the other hand a lower $\upsilon$ will result in more network traffic and hence increase the cost of distribution.
It seems sensible to require that the threshold should be choosen in such a way that it amortizes the cost of distribution. This claim relates to the field of amortization analysis, a common technique that is used to accomplish data structures that change size efficiently in terms of memory consupmtion and operational performance, i.e.\ for dynamic arrays \cite{mehldorn2008}.   

\subsubsection{Retraction}
\label{sec:pa-expansionretraction}
Consider a search tree with one level of children. Suppose that it receives multiple untag messages such that many of the entries in the object indexes on the leaves are removed. Let this continue until the cumulative size of the children object indexes drops below the threshold $\upsilon$ on the parent node. At this point, the benefits of distribution, namely storage equality, become negligible, while the costs of search remain high. Clearly, it would be more efficient to remove the children and return the leftover entries to the root. This process is called \textit{index retraction}.  

\subsection{Messaging}
\label{sec:messaging}
\subsubsection{Method of returning search results}
There are different approaches of returning results from the leaves of an index to the requester. One intuitive approach is to send results up the tree merging them at every parent until they are received at the root. Thus, the root can return a single message to the requester containing all of the results. The first problem here is that the results arrive asynchronously at every parent, so each parent must wait until it receives content from all of its children. The second problem is that a lot of bandwidth would be used in sending the results up the tree. The number of messages required for this is $\sum_{L=0}^H{C^L}$.
Nevertheless, by sending results to the requester directly from the leaves, we can save a substantial amount of bandwidth. The amount required to send 
 The total number of messages required for this is: $C^H$. Thus, the number of saved messages is: 
\begin{eqnarray}
 (\sum_{L=0}^H{C^L}) - C^H  =  \sum_{L=0}^{H-1}{C^L}  =  C^H-1
\end{eqnarray} 

\subsubsection{Request-reply protocol}

A request reply protocol is required for the case when a node needs to know if a requested action was executed successfully in some other part of the network. In particular distributed concurrency control maybe required to ensure correct results of concurrent operations \cite{coulouris2005}. For example, the distribution of a object index may only commit if each sub expansion to the children completed successfully. 

\subsubsection{Time-to-live for messages}

Network problems may occasionally delay search messages as they are routed towards object indexes of a keyword. If delays are considerable, it may be worthwhile to limit the period of their validity with a time-to-live. 

\subsection{Information Retrieval}
\subsubsection{Merging asynchronous results}
An expanded index responds to search messages with at least two result messages that arrive back asynchronously. Therefore, an mechanism capable of merging the overall search result should be established. When a user searches for more than one keyword at once the algorithm needs to be able to generate the intersection of the results from each keyword. 

\subsubsection{Ranking}
As the number of entries at an index grows, it becomes more difficult for end-users to manage the results and discover relevant entries within them. This problem could be solved by attaching a popularity rating to every index entry. The more users tag an object $obj$ under keyword $K$, the higher the rating of $obj$ will be in $K$'s index. When users retrieve data from $K$'s index, the results arrive sorted from most to least popular.

\subsection{Overloading}

\subsubsection{Bottlenecks}
\label{sec:pa-bottlenecks}
Bottlenecks describes a situation where a resource is at higher risk of overloading due to the design of the system. For example, in a system without replication the probability for handling a store request message at a root node of a tree is 1 whereas the probability at any other node in the tree is $1/C^L$. 
Replicating the root node, a mechanism that is provided by Pastry, reduces the probability for it having to handle store messages. 

\subsubsection{Security}
Potential overloading of resources caused by the behaviour of the user is a security risk (i.e.\ denial-of-service attacks) and requires special counter measurements. For example, the user should not be able to trigger the same search multiple times within a short period of time. This is a possible for future work and is described further in \ref{sec:future_security}.
